package demo.DataStrucAndAlgo.AlgorithmOfTen;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/7-08-07-16:07
 * @Description：demo.DataStrucAndAlgo.AlgorithmOfTen
 */
/*
最优收益问题：如下图，8个任务分布在0~11的时间段内，每个任务对应的收益不同，
（1号任务，收益5），在一个时间段内只能做一件任务。问在8个任务中最优收益为多少？
任务一     时间段：1~4      收益：5
任务二     时间段：3~5      收益：1
任务三     时间段：0~6      收益：8
任务四     时间段：4~7      收益：4
任务五     时间段：3~8      收益：6
任务六     时间段：5~9      收益：3
任务七     时间段：6~10      收益：2
任务八     时间段：8~11      收益：4
 */
public class DP_04 {
    static int[][] taskTime = {{0,0},{1,4},{3,5},{0,6},{4,7},{3,8},{5,9},{6,10},{8,11}};
    static int[] income = {0,5,1,8,4,6,3,2,4};
    public static void main(String[] args) {
        System.out.println(OPT(8));
    }

    /**
     * 动态规划：递归计算出最优解
     * @param i   开始计算的任务序号
     * @return    最优解
     */
    public static int OPT(int i) {
        if(i == 0){
            return 0;
        }
        int A = income[i] + OPT(prev(i));    //方案一：选择当前任务
        int B = OPT(i-1);   //方案2：不选当前任务
            return Math.max(A,B);
    }

    /**
     * 根据任务时常获取当前任务之前的最近可用任务
     * @param i   当前任务
     * @return    最近可用任务
     */
    public static int prev(int i) {
        int value = taskTime[i][0];
        while(true){
            if(i == 1){
                return 0;
            }
            if(value >= taskTime[i][1]){
                return i-1;
            }
            i--;
        }
    }
}
